#include <bits/stdc++.h>

using namespace std;

// 监控二叉树
// 给定一个二叉树，我们在树的节点上安装摄像头
// 节点上的每个摄影头都可以监视其父对象、自身及其直接子对象
// 计算监控树的所有节点所需的最小摄像头数量
// 测试链接 : https://leetcode.cn/problems/binary-tree-cameras/

// 不需要提交这个类
struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution 
{
private:
    // 遍历过程中一旦需要放置相机，ans++
    int ans;

	// 递归含义
	// 假设x上方一定有父亲的情况下，这个假设很重要
	// x为头的整棵树，最终想都覆盖，
	// 并且想使用最少的摄像头，x应该是什么样的状态
	// 返回值含义
	// 0: x是无覆盖的状态，x下方的节点都已经被覆盖
	// 1: x是覆盖状态，x上没摄像头，x下方的节点都已经被覆盖
	// 2: x是覆盖状态，x上有摄像头，x下方的节点都已经被覆盖
    int f(TreeNode* x)
    {
        if(x == nullptr) return 1;
        
        int left = f(x->left);
        int right = f(x->right);
        // 左孩子或右孩子没有被摄像头覆盖到，那么 x 一定要安装摄像头
        if(left == 0 || right == 0)
        {
            ++ans;
            return 2;
        }
        // 左孩子和右孩子都被摄像头覆盖到了，那么此时
        // 让 x 的父亲来安装摄像头，这样更省摄像头
        if(left == 1 && right == 1) return 0;
        // 其余情况为左右孩子至少有一个安装了摄像头，此时 x 
        // 能够被覆盖到，不需要安装摄像头
        return 1;
    }

public:
    int minCameraCover(TreeNode* root) 
    {
        ans = 0;
        // root 的子树都被摄像头覆盖到了，只有 root 没有
        // 被摄像头覆盖到，因此要在 root 上安装一个摄像头
        if(f(root) == 0) ++ans;
        return ans; 
    }
};